package org.demo.algorithm;

import java.io.PrintWriter;

/**
 * 计算大数的阶乘
 * 参考：http://www.cnblogs.com/phinecos/archive/2009/10/06/1578411.html
 * @author  
 * @date    2011-4-8
 * @file    org.demo.algorithm.Fact.java
 */
public class Fact {

	/**
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args) throws Exception {
		
		// 开始时间
		long start = System.currentTimeMillis();
		
		// 1. 使用系统 BigInteger 进行计算 
		java.math.BigInteger result = new java.math.BigInteger(String.valueOf(1));
		for (int i=2; i<10000; i++){
			result = result.multiply(new java.math.BigInteger(String.valueOf(i)));
		}
		PrintWriter pw = new PrintWriter("d:\\Temp\\result.txt");
		pw.write(result.toString());
		pw.flush();
		pw.close();
		
		// 2. 使用自定义 BigInteger 进行计算
		BigInteger result2 = new BigInteger(1);
		for (int i=2; i<10000; i++){
			result2 = result2.multiply(new BigInteger(i));
		}
		PrintWriter pw2 = new PrintWriter("d:\\Temp\\result-2.txt");
		pw2.write(result2.toString());
		pw2.flush();
		pw2.close();
		
		// 结束时间
		long finish = System.currentTimeMillis();
		System.out.println((finish - start)/1000);
				
	}
}
/**
 * 自定义大整数
 * @author 
 *
 */
class BigInteger{

	// 分组个数
    private static int MAX_GROUPS = 20000;
    // 每组最大值
    private static int GROUP_MAX = 9999;
    // 每组长度
    private static int GROUP_LEN = 4;
    
    // 存储数据
    private int data[];
    // 数组已经使用的长度
    private int len;
    
    /**
     * 分段存储大整数
     * @param num
     */
    public BigInteger(int num){
        data = new int[MAX_GROUPS];
        len = 0;
        
        int tmp = num;
        while (tmp > GROUP_MAX){
            data[len++] = tmp % (GROUP_MAX +1);
            tmp = tmp / (GROUP_MAX + 1);
        }
        if (tmp > 0){
            data[len++] = tmp;
        }
    }
    /**
     * 对大整数进行分段相乘
     * @param other
     * @return
     */
    public BigInteger multiply(BigInteger other){
        BigInteger result = new BigInteger(0);
        // tmp 临时数据, up 进位数据
        int tmp, up;
        
        int i = 0, j = 0;
        for (i=0; i<len; i++){    
        	up = 0;
            for (j=0; j<other.getLength(); j++){
                tmp = data[i] * other.getData(j) + result.getData(i+j) + up;
                if (tmp > GROUP_MAX){
                    result.setData(i+j, tmp % (GROUP_MAX + 1));
                    up = tmp/(GROUP_MAX + 1);
                } else {
                    result.setData(i+j, tmp);
                    up = 0;
                }
            }
            if (up != 0){
            	result.setData(i+j, up);
            }
        }
        int length = i+j;
        while (length > 1 && result.getData(length - 1) == 0){
            length--;
        }
        result.setLength(length);
        return result;
    }
    
    public int getLength(){
        return len;
    }
    
    public void setLength(int length){
        len = length;
    }
    
    public int getData(int index){
        return data[index];
    }
    
    public void setData(int index, int d){
        data[index] = d;
    }
    
    /**
     * 获取整数的位数
     * @param number
     * @return
     */
    public int getNumberLength(int number){
        int length = 1;
        while (number/10 != 0){
            length++;
            number = number/10;
        }
        return length;
    }
    
    /**
     * 返回大整数
     */
    public String toString(){
    	StringBuilder sb = new StringBuilder();
        for (int i=len-1; i>=0; i--){
            int zeroLength = GROUP_LEN - getNumberLength(data[i]);
            for (int j=0; j< zeroLength; j++){
                sb.append(0);
            }
            sb.append(data[i]);
        }        
        while (sb.length() > 1 && sb.charAt(0) == '0'){
        	sb.deleteCharAt(0);
        }
        return sb.toString();
    }
}
